#include <vector>

using namespace std;

class Solution {
private:
    int merge_sort(vector<int>& nums, vector<int>& tmp, int left, int right) {
        if (left >= right) {
            return 0;
        }
        int middle = (left + right) / 2;
        int ans = merge_sort(nums, tmp, left, middle) + merge_sort(nums, tmp, middle + 1, right);
        int i = left;
        int j = middle + 1;
        int p = left;
        while (i <= middle && j <= right) {
            if (nums[i] <= nums[j]) {
                tmp[p] = nums[i];
                i++;
                ans += (j - middle - 1);
            } else {
                tmp[p] = nums[j];
                j++;
            }
            p++;
        }
        for (; i <= middle; i++) {
            tmp[p++] = nums[i];
            ans += (j - middle - 1);
        }
        for (; j <= right; j++) {
            tmp[p++] = nums[j];
        }
        copy(tmp.begin() + left, tmp.begin() + right + 1, nums.begin() + left);
        return ans;
    }
public:
    int reversePairs(vector<int>& nums) {
        vector<int> tmp(nums.size());
        return merge_sort(nums, tmp, 0, nums.size() - 1);
    }
};